import bisect
class Solution:
    def maxIncreasingCells(self, mat) -> int:
        m = len(mat)
        n = len(mat[0])
        row_st = []
        col_st = []
        for i in range(m):
            new_row = [[mat[i][j], j] for j in range(n)]
            new_row.sort()
            row_st.append(new_row)
        for j in range(n):
            new_row = [[mat[i][j], i] for i in range(m)]
            new_row.sort()
            col_st.append(new_row)
        ans_dict = {}
        def dfs(i, j):
            if (i, j) in ans_dict:
                return ans_dict[(i, j)]
            else:
                row_next_index = bisect.bisect_right(row_st[i], [mat[i][j], n])
                col_next_index = bisect.bisect_right(col_st[j], [mat[i][j], m])
                next_dict = []
                if row_next_index < n:
                    max_val = 0
                    last_val = row_st[i][row_next_index][0]
                    
                    while row_next_index < n:
                        if row_st[i][row_next_index][0] == last_val:
                            next_j = row_st[i][row_next_index][1]
                            max_val = max(max_val, dfs(i, next_j))
                            row_next_index += 1
                        else:
                            break
                    next_dict.append(max_val)
                if col_next_index < m:
                    max_val = 0
                    last_val = col_st[j][col_next_index][0]
                    while col_next_index < m:
                        if col_st[j][col_next_index][0] == last_val:
                            next_i = col_st[j][col_next_index][1]
                            max_val = max(max_val, dfs(next_i, j))
                            col_next_index += 1
                        else:
                            break
                    next_dict.append(max_val)
                if next_dict:
                    return_val = max(next_dict) + 1
                else:
                    return_val = 1
                ans_dict[(i, j)] = return_val
                return return_val
        for i in range(m):
            for j in range(n):
                dfs(i, j)

        return max(ans_dict.values())

data = Solution()

# mat = [[7,6,3],[-7,-5,6],[-7,0,-4],[6,6,0],[-8,6,0]]
mat = [[3,1],[3,4]]
print(data.maxIncreasingCells(mat))